package net.lee.algorithm.tree;

import sun.dc.pr.PRError;

import javax.swing.plaf.nimbus.State;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

public class TreeInfo {

    public static void main(String args[]) {
        TreeNode treeNode = getTree();
        //随便写的遍历
//        Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
//        treeNodeStack.push(treeNode);
//        List<TreeNode> treeNodes = new ArrayList<TreeNode>();
//        treeNodes.add(treeNode);
//        treeNodes.addAll(getALLTreeNode(treeNodeStack));

        //使用队列实现的广度优先搜索遍历
//        Queue<TreeNode> treeNodeQueue = new ArrayDeque<TreeNode>();
//        treeNodeQueue.offer(treeNode);
//         List<TreeNode> treeNodes = new ArrayList<TreeNode>();
//        treeNodes.add(treeNode);
//        treeNodes.addAll(getAllTreeNodeScope(treeNodeQueue));
//        Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
//        treeNodeStack.push(treeNode);
//        List<TreeNode> treeNodeList = new ArrayList<>();
//        treeNodeList =   getAllTreeNodeScope(treeNode,treeNodeList);
//        if (treeNodeList != null) {
//            for (TreeNode treenode : treeNodeList
//                    ) {
//                System.out.print(treenode.getValue() + "-");
//            }
//        }
        System.out.println(" ");
        System.out.println("------------------------------------------------------------------");
//        depthOrderTraversal(treeNode);
        List<TreeNode> resultNodes = new ArrayList<>();
        resultNodes = scorpOrderTraversal(treeNode);

        if (resultNodes != null) {
            for (TreeNode treenode : resultNodes
                    ) {
                System.out.print(treenode.getValue() + "-");
            }
        }

    }

    /**
     * 深度优先遍历
     * @param treeNode
     * @param treeNodes
     * @return
     */
    public static List<TreeNode> getAllTreeNodeDeep(TreeNode treeNode, List<TreeNode> treeNodes) {

        if (treeNode != null && treeNodes != null && !treeNodes.contains(treeNode)) {
            treeNodes.add(treeNode);
        }
        if (treeNode.getLeftNode() != null && !treeNodes.contains(treeNode.getLeftNode())) {
            //treeNodeStack.push(treeNode.getLeftNode());
            getAllTreeNodeDeep(treeNode.getLeftNode(), treeNodes);
        }
        if (treeNode.getRightNode() != null && !treeNodes.contains(treeNode.getRightNode())) {
            //treeNodeStack.push(treeNode.getRightNode());
            getAllTreeNodeDeep(treeNode.getRightNode(), treeNodes);
        }
        if (treeNode.getParentNode() != null) {
            //treeNodeStack.push(treeNode.getParentNode());
            getAllTreeNodeDeep(treeNode.getParentNode(), treeNodes);
        }

        return treeNodes;
    }

    /**
     * 广度优先遍历 队列
     * @param treeNode
     * @return
     */
    public static List<TreeNode> scorpOrderTraversal(TreeNode treeNode) {
        List<TreeNode> treeNodes = new ArrayList<>();
        if (treeNode == null) {
            return null;
        }
        Queue<TreeNode> treeNodeQueue = new ArrayDeque<>();
        treeNodeQueue.add(treeNode);
        while (!treeNodeQueue.isEmpty()) {
            treeNode = treeNodeQueue.remove();
            treeNodes.add(treeNode);
            if (treeNode.getLeftNode() != null) {
                treeNodeQueue.add(treeNode.getLeftNode());
            }
            if (treeNode.getRightNode() != null) {
                treeNodeQueue.add(treeNode.getRightNode());
            }

        }
        return treeNodes;
    }

    /**
     * 深度优先遍历，相当于先根遍历
     * 采用非递归实现
     * 需要辅助数据结构：栈
     */
    public static void depthOrderTraversal(TreeNode treeNode) {
        if (treeNode == null) {
            System.out.println("empty tree");
            return;
        }
        ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
        stack.push(treeNode);
        while (stack.isEmpty() == false) {
            TreeNode node = stack.pop();
            System.out.print(node.getValue() + "    ");
            if (node.getRightNode() != null) {
                stack.push(node.getRightNode());
            }
            if (node.getLeftNode() != null) {
                stack.push(node.getLeftNode());
            }
        }
        System.out.print("\n");
    }

    /**
     * 广度优先遍历， 目前没发现不需要使用栈的递归方法
     * @param treeNodeQueue
     * @return
     */
    public static List<TreeNode> getAllTreeNodeScope(Queue<TreeNode> treeNodeQueue) {
        List<TreeNode> treeNodes = new ArrayList<TreeNode>();
        List<TreeNode> addResult = new ArrayList<TreeNode>();
        addResult = getNodes(treeNodeQueue);
        treeNodes.addAll(addResult);
        if (treeNodeQueue.size() > 0) {
            addResult = getAllTreeNodeScope(treeNodeQueue);
            treeNodes.addAll(addResult);
        }

        return treeNodes;
    }

    public static List<TreeNode> getALLTreeNode(Stack<TreeNode> treeNodeStack) {
        List<TreeNode> treeNodes = new ArrayList<TreeNode>();
        List<TreeNode> addResult = new ArrayList<TreeNode>();
        addResult = getNodes(treeNodeStack);
        treeNodes.addAll(addResult);
        if (treeNodeStack.size() > 0) {
            addResult = getALLTreeNode(treeNodeStack);
            treeNodes.addAll(addResult);
        }

        return treeNodes;
    }

    private static List<TreeNode> getNodes(Queue<TreeNode> treeNodeQueue) {
        TreeNode treeNode = treeNodeQueue.poll();
        List<TreeNode> nodes = new ArrayList<TreeNode>();


        if (treeNode.getRightNode() != null) {
            nodes.add(treeNode.getRightNode());
            treeNodeQueue.offer(treeNode.getRightNode());
        }

        if (treeNode.getLeftNode() != null) {
            nodes.add(treeNode.getLeftNode());
            treeNodeQueue.offer(treeNode.getLeftNode());
        }

        return nodes;

    }



    private static List<TreeNode> getNodes(Stack<TreeNode> treeNodeStack) {
        TreeNode treeNode = treeNodeStack.pop();
        List<TreeNode> nodes = new ArrayList<TreeNode>();
        if (treeNode.getLeftNode() != null) {
            nodes.add(treeNode.getLeftNode());
            treeNodeStack.push(treeNode.getLeftNode());
        }

        if (treeNode.getRightNode() != null) {
            nodes.add(treeNode.getRightNode());
            treeNodeStack.push(treeNode.getRightNode());
        }

        return nodes;
    }


    public static TreeNode getTree() {
        TreeNode root = new TreeNode();
        root.setValue("A");
        TreeNode b = new TreeNode();
        TreeNode c = new TreeNode();
        TreeNode d = new TreeNode();
        TreeNode e = new TreeNode();
        TreeNode f = new TreeNode();
        TreeNode g = new TreeNode();
        TreeNode h = new TreeNode();
        b.setValue("B");
        c.setValue("C");
        d.setValue("D");
        e.setValue("E");
        f.setValue("F");
        g.setValue("G");
        h.setValue("H");
        root.setLeftNode(b);
        root.setRightNode(c);
        b.setParentNode(root);
        b.setLeftNode(d);
        b.setRightNode(e);
        c.setParentNode(root);
        c.setLeftNode(f);
        c.setRightNode(g);
        d.setParentNode(b);
        d.setLeftNode(h);
        e.setParentNode(b);
        f.setParentNode(c);
        g.setParentNode(c);
        h.setParentNode(d);
        return root;
    }
}
